package 栈与队列;

import java.util.Stack;

/**
 *155. 最小栈
 *
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * 实现 MinStack 类:
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素。
 *
 * 思路：
 *  为了在常数时间内获取栈中的最小元素，我们需要维护一个辅助栈，该栈的顶部元素始终为当前栈中的最小元素。
 *  主栈：用于存储所有元素。
 *  辅助栈：用于存储当前栈中的最小元素。
    具体操作如下：
    - push(x)
        - 将 x 压入主栈；
        - 如果辅助栈为空，或者x小于等于辅助栈的栈顶元素，则将x压入辅助栈中。
    - pop（x）
        - 弹出主栈的栈顶元素；
        - 如果弹出的元素等于辅助栈栈顶的元素，则同时弹出辅助栈的栈顶元素。
 */
public class L_155 {

}

class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack; // 辅助栈

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        // 判断是否为空，或者当前元素是否小于等于辅助栈的栈顶元素,就压入辅助栈中
        if(minStack.empty() || val <= minStack.peek()){
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        Integer pop = stack.pop();
        // 如果弹出的元素等于辅助栈的栈顶元素，也弹出辅助栈
        if (pop.equals(minStack.peek())) { // 使用equals是因为Integer的默认缓存区，-128~127的数字，超出了就是新对象
            minStack.pop();
        }
    }

    public int top() {
        if (!stack.isEmpty()) {
            return stack.peek();
        }
        throw new RuntimeException("Stack is empty");
    }

    public int getMin() {
        if (!minStack.isEmpty()) {
            return minStack.peek();
        }
        throw new RuntimeException("Stack is empty");
    }
}